package com.theeviljames.maths;

import java.util.Arrays;
import java.util.Random;

public class DynamicMatrixChain {

	private static final Random rand = new Random();
	private static final IMatrixOps m = MatrixOps.getMatrixOps();
	
	public static final double[][] multiply(double[][][] matrices){
		return null;
	}
	
	public static final int noOfParens(int n){
		if(n==1)return 1;
		else{
			int sum = 0;
			for(int i = 1; i < n; i++){
				sum += (noOfParens(i)*noOfParens(n-i));
			}
			return sum;
		}
	}
	
	public static final int[][][] matrixChainOrder(int[] p){
		int n = p.length-1;
		int[][] m = new int[n][];
		int[][] s = new int[n][];
		for(int i = 0; i <n; i++){
			m[i] = new int[n-i];
			s[i] = new int[n-i];
			//just to make it explicit (remove)
			m[i][0] = 1;
		}
		for(int l = 1; l < n; l++){
			for(int i = 0; i < n-l; i++){
				int j = i+l-1;
				m[i][j] = Integer.MAX_VALUE;
				for(int k = i; k < j-1; k++){
					int q = m[i][k]+m[k+1][j]+(p[i-1]*p[k]*p[j]);
					if(q<m[i][j]){
						m[i][j]=q;
						s[i][j]=k;
					}
				}
			}
		}
		return new int[][][]{m,s};
	}
	
	private static void print(String legend,int[][] a) {
		// TODO Auto-generated method stub
		for(int[]b:a)System.out.println("\n"+legend+"\n"+Arrays.toString(b));
		System.out.println();
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//System.out.println(noOfParens(4));
		double[][] a1 = new double[30][35];
		for(int i = 0; i< a1.length; i++)for(int j = 0; j< a1[i].length; j++)a1[i][j]=rand.nextDouble()*10;
		
		double[][] a2 = new double[35][15];
		for(int i = 0; i< a2.length; i++)for(int j = 0; j< a2[i].length; j++)a2[i][j]=rand.nextDouble()*10;
		
		double[][] a3 = new double[15][5];
		for(int i = 0; i< a3.length; i++)for(int j = 0; j< a3[i].length; j++)a3[i][j]=rand.nextDouble()*10;
		
		double[][] a4 = new double[5][10];
		for(int i = 0; i< a4.length; i++)for(int j = 0; j< a4[i].length; j++)a4[i][j]=rand.nextDouble()*10;
		
		double[][] a5 = new double[10][20];
		for(int i = 0; i< a5.length; i++)for(int j = 0; j< a5[i].length; j++)a5[i][j]=rand.nextDouble()*10;
		
		double[][] a6 = new double[20][25];
		for(int i = 0; i< a6.length; i++)for(int j = 0; j< a6[i].length; j++)a6[i][j]=rand.nextDouble()*10;
		
		m.print(a1);
		m.print(a2);
		m.print(a3);
		m.print(a4);
		m.print(a5);
		m.print(a6);
		
		int[] matrixDims = new int[7];
		matrixDims[0]=a1.length;
		matrixDims[1]=a1[0].length;
		matrixDims[2]=a2[0].length;
		matrixDims[3]=a3[0].length;
		matrixDims[4]=a4[0].length;
		matrixDims[5]=a5[0].length;
		matrixDims[6]=a6[0].length;
		
		System.out.println(Arrays.toString(matrixDims)+"\n");
		
		int[][][] ms = matrixChainOrder(matrixDims);
		print("M",ms[0]);
		print("S",ms[1]);
		
	}

}
